<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><link rel="stylesheet" type="text/css" href="style.css" /><script type="text/javascript" src="highlight.js"></script></head><body><pre><span class="hs-pragma">{-# LANGUAGE CPP #-}</span><span class="hs-cpp">
#ifdef __HADDOCK_VERSION__
</span><span class="hs-pragma">{-# OPTIONS_GHC -Wno-unused-imports #-}</span><span class="hs-cpp">
#endif
</span><span class="hs-cpp">
#include &quot;containers.h&quot;
</span><span>
</span><span id="line-8"></span><span class="hs-comment">-----------------------------------------------------------------------------</span><span>
</span><span id="line-9"></span><span class="hs-comment">-- |</span><span>
</span><span id="line-10"></span><span class="hs-comment">-- Module      :  Data.Sequence</span><span>
</span><span id="line-11"></span><span class="hs-comment">-- Copyright   :  (c) Ross Paterson 2005</span><span>
</span><span id="line-12"></span><span class="hs-comment">--                (c) Louis Wasserman 2009</span><span>
</span><span id="line-13"></span><span class="hs-comment">--                (c) Bertram Felgenhauer, David Feuer, Ross Paterson, and</span><span>
</span><span id="line-14"></span><span class="hs-comment">--                    Milan Straka 2014</span><span>
</span><span id="line-15"></span><span class="hs-comment">-- License     :  BSD-style</span><span>
</span><span id="line-16"></span><span class="hs-comment">-- Maintainer  :  libraries@haskell.org</span><span>
</span><span id="line-17"></span><span class="hs-comment">-- Portability :  portable</span><span>
</span><span id="line-18"></span><span class="hs-comment">--</span><span>
</span><span id="line-19"></span><span class="hs-comment">-- = Finite sequences</span><span>
</span><span id="line-20"></span><span class="hs-comment">--</span><span>
</span><span id="line-21"></span><span class="hs-comment">-- The @'Seq' a@ type represents a finite sequence of values of</span><span>
</span><span id="line-22"></span><span class="hs-comment">-- type @a@.</span><span>
</span><span id="line-23"></span><span class="hs-comment">--</span><span>
</span><span id="line-24"></span><span class="hs-comment">-- Sequences generally behave very much like lists.</span><span>
</span><span id="line-25"></span><span class="hs-comment">--</span><span>
</span><span id="line-26"></span><span class="hs-comment">-- * The class instances for sequences are all based very closely on those for</span><span>
</span><span id="line-27"></span><span class="hs-comment">-- lists.</span><span>
</span><span id="line-28"></span><span class="hs-comment">--</span><span>
</span><span id="line-29"></span><span class="hs-comment">-- * Many functions in this module have the same names as functions in</span><span>
</span><span id="line-30"></span><span class="hs-comment">-- the &quot;Prelude&quot; or in &quot;Data.List&quot;. In almost all cases, these functions</span><span>
</span><span id="line-31"></span><span class="hs-comment">-- behave analogously. For example, 'filter' filters a sequence in exactly the</span><span>
</span><span id="line-32"></span><span class="hs-comment">-- same way that @&quot;Prelude&quot;.'Prelude.filter'@ filters a list. The only major</span><span>
</span><span id="line-33"></span><span class="hs-comment">-- exception is the 'lookup' function, which is based on the function by</span><span>
</span><span id="line-34"></span><span class="hs-comment">-- that name in &quot;Data.IntMap&quot; rather than the one in &quot;Prelude&quot;.</span><span>
</span><span id="line-35"></span><span class="hs-comment">--</span><span>
</span><span id="line-36"></span><span class="hs-comment">-- There are two major differences between sequences and lists:</span><span>
</span><span id="line-37"></span><span class="hs-comment">--</span><span>
</span><span id="line-38"></span><span class="hs-comment">-- * Sequences support a wider variety of efficient operations than</span><span>
</span><span id="line-39"></span><span class="hs-comment">-- do lists. Notably, they offer</span><span>
</span><span id="line-40"></span><span class="hs-comment">--</span><span>
</span><span id="line-41"></span><span class="hs-comment">--     * Constant-time access to both the front and the rear with</span><span>
</span><span id="line-42"></span><span class="hs-comment">--     '&lt;|', '|&gt;', 'viewl', 'viewr'. For recent GHC versions, this can</span><span>
</span><span id="line-43"></span><span class="hs-comment">--     be done more conveniently using the bidirectional patterns 'Empty',</span><span>
</span><span id="line-44"></span><span class="hs-comment">--     ':&lt;|', and ':|&gt;'. See the detailed explanation in the \&quot;Pattern synonyms\&quot;</span><span>
</span><span id="line-45"></span><span class="hs-comment">--     section.</span><span>
</span><span id="line-46"></span><span class="hs-comment">--     * Logarithmic-time concatenation with '&gt;&lt;'</span><span>
</span><span id="line-47"></span><span class="hs-comment">--     * Logarithmic-time splitting with 'splitAt', 'take' and 'drop'</span><span>
</span><span id="line-48"></span><span class="hs-comment">--     * Logarithmic-time access to any element with</span><span>
</span><span id="line-49"></span><span class="hs-comment">--     'lookup', '!?', 'index', 'insertAt', 'deleteAt', 'adjust'', and 'update'</span><span>
</span><span id="line-50"></span><span class="hs-comment">--</span><span>
</span><span id="line-51"></span><span class="hs-comment">--   Note that sequences are typically /slower/ than lists when using only</span><span>
</span><span id="line-52"></span><span class="hs-comment">--   operations for which they have the same big-\(O\) complexity: sequences</span><span>
</span><span id="line-53"></span><span class="hs-comment">--   make rather mediocre stacks!</span><span>
</span><span id="line-54"></span><span class="hs-comment">--</span><span>
</span><span id="line-55"></span><span class="hs-comment">-- * Whereas lists can be either finite or infinite, sequences are</span><span>
</span><span id="line-56"></span><span class="hs-comment">-- always finite. As a result, a sequence is strict in its</span><span>
</span><span id="line-57"></span><span class="hs-comment">-- length. Ignoring efficiency, you can imagine that 'Seq' is defined</span><span>
</span><span id="line-58"></span><span class="hs-comment">--</span><span>
</span><span id="line-59"></span><span class="hs-comment">--     @ data Seq a = Empty | a :&lt;| !(Seq a) @</span><span>
</span><span id="line-60"></span><span class="hs-comment">--</span><span>
</span><span id="line-61"></span><span class="hs-comment">--     This means that many operations on sequences are stricter than</span><span>
</span><span id="line-62"></span><span class="hs-comment">--     those on lists. For example,</span><span>
</span><span id="line-63"></span><span class="hs-comment">--</span><span>
</span><span id="line-64"></span><span class="hs-comment">--     @ (1 : undefined) !! 0 = 1 @</span><span>
</span><span id="line-65"></span><span class="hs-comment">--</span><span>
</span><span id="line-66"></span><span class="hs-comment">--     but</span><span>
</span><span id="line-67"></span><span class="hs-comment">--</span><span>
</span><span id="line-68"></span><span class="hs-comment">--     @ (1 :&lt;| undefined) ``index`` 0 = undefined @</span><span>
</span><span id="line-69"></span><span class="hs-comment">--</span><span>
</span><span id="line-70"></span><span class="hs-comment">-- Sequences may also be compared to immutable</span><span>
</span><span id="line-71"></span><span class="hs-comment">-- [arrays](https://hackage.haskell.org/package/array)</span><span>
</span><span id="line-72"></span><span class="hs-comment">-- or [vectors](https://hackage.haskell.org/package/vector).</span><span>
</span><span id="line-73"></span><span class="hs-comment">-- Like these structures, sequences support fast indexing,</span><span>
</span><span id="line-74"></span><span class="hs-comment">-- although not as fast. But editing an immutable array or vector,</span><span>
</span><span id="line-75"></span><span class="hs-comment">-- or combining it with another, generally requires copying the</span><span>
</span><span id="line-76"></span><span class="hs-comment">-- entire structure; sequences generally avoid that, copying only</span><span>
</span><span id="line-77"></span><span class="hs-comment">-- the portion that has changed.</span><span>
</span><span id="line-78"></span><span class="hs-comment">--</span><span>
</span><span id="line-79"></span><span class="hs-comment">-- == Detailed performance information</span><span>
</span><span id="line-80"></span><span class="hs-comment">--</span><span>
</span><span id="line-81"></span><span class="hs-comment">-- An amortized running time is given for each operation, with /n/ referring</span><span>
</span><span id="line-82"></span><span class="hs-comment">-- to the length of the sequence and /i/ being the integral index used by</span><span>
</span><span id="line-83"></span><span class="hs-comment">-- some operations. These bounds hold even in a persistent (shared) setting.</span><span>
</span><span id="line-84"></span><span class="hs-comment">--</span><span>
</span><span id="line-85"></span><span class="hs-comment">-- Despite sequences being structurally strict from a semantic standpoint,</span><span>
</span><span id="line-86"></span><span class="hs-comment">-- they are in fact implemented using laziness internally. As a result,</span><span>
</span><span id="line-87"></span><span class="hs-comment">-- many operations can be performed /incrementally/, producing their results</span><span>
</span><span id="line-88"></span><span class="hs-comment">-- as they are demanded. This greatly improves performance in some cases. These</span><span>
</span><span id="line-89"></span><span class="hs-comment">-- functions include</span><span>
</span><span id="line-90"></span><span class="hs-comment">--</span><span>
</span><span id="line-91"></span><span class="hs-comment">-- * The 'Functor' methods 'fmap' and '&lt;$', along with 'mapWithIndex'</span><span>
</span><span id="line-92"></span><span class="hs-comment">-- * The 'Applicative' methods '&lt;*&gt;', '*&gt;', and '&lt;*'</span><span>
</span><span id="line-93"></span><span class="hs-comment">-- * The zips: 'zipWith', 'zip', etc.</span><span>
</span><span id="line-94"></span><span class="hs-comment">-- * 'inits', 'tails'</span><span>
</span><span id="line-95"></span><span class="hs-comment">-- * 'fromFunction', 'replicate', 'intersperse', and 'cycleTaking'</span><span>
</span><span id="line-96"></span><span class="hs-comment">-- * 'reverse'</span><span>
</span><span id="line-97"></span><span class="hs-comment">-- * 'chunksOf'</span><span>
</span><span id="line-98"></span><span class="hs-comment">--</span><span>
</span><span id="line-99"></span><span class="hs-comment">-- Note that the 'Monad' method, '&gt;&gt;=', is not particularly lazy. It will</span><span>
</span><span id="line-100"></span><span class="hs-comment">-- take time proportional to the sum of the logarithms of the individual</span><span>
</span><span id="line-101"></span><span class="hs-comment">-- result sequences to produce anything whatsoever.</span><span>
</span><span id="line-102"></span><span class="hs-comment">--</span><span>
</span><span id="line-103"></span><span class="hs-comment">-- Several functions take special advantage of sharing to produce</span><span>
</span><span id="line-104"></span><span class="hs-comment">-- results using much less time and memory than one might expect. These</span><span>
</span><span id="line-105"></span><span class="hs-comment">-- are documented individually for functions, but also include certain</span><span>
</span><span id="line-106"></span><span class="hs-comment">-- class methods:</span><span>
</span><span id="line-107"></span><span class="hs-comment">--</span><span>
</span><span id="line-108"></span><span class="hs-comment">-- '&lt;$' and '*&gt;' each take time and space proportional</span><span>
</span><span id="line-109"></span><span class="hs-comment">-- to the logarithm of the size of their result.</span><span>
</span><span id="line-110"></span><span class="hs-comment">--</span><span>
</span><span id="line-111"></span><span class="hs-comment">-- '&lt;*' takes time and space proportional to the product of the length</span><span>
</span><span id="line-112"></span><span class="hs-comment">-- of its first argument and the logarithm of the length of its second</span><span>
</span><span id="line-113"></span><span class="hs-comment">-- argument.</span><span>
</span><span id="line-114"></span><span class="hs-comment">--</span><span>
</span><span id="line-115"></span><span class="hs-comment">-- == Warning</span><span>
</span><span id="line-116"></span><span class="hs-comment">--</span><span>
</span><span id="line-117"></span><span class="hs-comment">-- The size of a 'Seq' must not exceed @maxBound::Int@. Violation</span><span>
</span><span id="line-118"></span><span class="hs-comment">-- of this condition is not detected and if the size limit is exceeded, the</span><span>
</span><span id="line-119"></span><span class="hs-comment">-- behaviour of the sequence is undefined. This is unlikely to occur in most</span><span>
</span><span id="line-120"></span><span class="hs-comment">-- applications, but some care may be required when using '&gt;&lt;', '&lt;*&gt;', '*&gt;', or</span><span>
</span><span id="line-121"></span><span class="hs-comment">-- '&gt;&gt;', particularly repeatedly and particularly in combination with</span><span>
</span><span id="line-122"></span><span class="hs-comment">-- 'replicate' or 'fromFunction'.</span><span>
</span><span id="line-123"></span><span class="hs-comment">--</span><span>
</span><span id="line-124"></span><span class="hs-comment">-- == Implementation</span><span>
</span><span id="line-125"></span><span class="hs-comment">--</span><span>
</span><span id="line-126"></span><span class="hs-comment">-- The implementation uses 2-3 finger trees annotated with sizes,</span><span>
</span><span id="line-127"></span><span class="hs-comment">-- as described in section 4.2 of</span><span>
</span><span id="line-128"></span><span class="hs-comment">--</span><span>
</span><span id="line-129"></span><span class="hs-comment">--    * Ralf Hinze and Ross Paterson,</span><span>
</span><span id="line-130"></span><span class="hs-comment">--      [\&quot;Finger trees: a simple general-purpose data structure\&quot;]</span><span>
</span><span id="line-131"></span><span class="hs-comment">--      (http://staff.city.ac.uk/~ross/papers/FingerTree.html),</span><span>
</span><span id="line-132"></span><span class="hs-comment">--      /Journal of Functional Programming/ 16:2 (2006) pp 197-217.</span><span>
</span><span id="line-133"></span><span class="hs-comment">--</span><span>
</span><span id="line-134"></span><span class="hs-comment">-----------------------------------------------------------------------------</span><span>
</span><span id="line-135"></span><span>
</span><span id="line-136"></span><span>
</span><span id="line-137"></span><span class="hs-keyword">module</span><span> </span><span class="hs-identifier">Data.Sequence</span><span> </span><span class="hs-special">(</span><span>
</span><span id="line-138"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Finite sequences</span></span><span class="hs-cpp">
#if defined(DEFINE_PATTERN_SYNONYMS)
</span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#Seq"><span class="hs-identifier">Seq</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.Sequence.Internal.html#Empty"><span class="hs-identifier">Empty</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#%3A%3C%7C"><span class="hs-operator">(:&lt;|)</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html#%3A%7C%3E"><span class="hs-operator">(:|&gt;)</span></a></span><span class="hs-special">)</span><span class="hs-special">,</span><span>
</span><span id="line-141"></span><span>    </span><span class="annot"><span class="hs-comment">-- $patterns</span></span><span class="hs-cpp">
#else
</span><span>    </span><span class="hs-identifier">Seq</span><span class="hs-special">,</span><span class="hs-cpp">
#endif
</span><span>    </span><span class="annot"><span class="hs-comment">-- * Construction</span></span><span>
</span><span id="line-146"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#empty"><span class="hs-identifier">empty</span></a></span><span class="hs-special">,</span><span>          </span><span class="hs-comment">-- :: Seq a</span><span>
</span><span id="line-147"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#singleton"><span class="hs-identifier">singleton</span></a></span><span class="hs-special">,</span><span>      </span><span class="hs-comment">-- :: a -&gt; Seq a</span><span>
</span><span id="line-148"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#%3C%7C"><span class="hs-operator">(&lt;|)</span></a></span><span class="hs-special">,</span><span>           </span><span class="hs-comment">-- :: a -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-149"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#%7C%3E"><span class="hs-operator">(|&gt;)</span></a></span><span class="hs-special">,</span><span>           </span><span class="hs-comment">-- :: Seq a -&gt; a -&gt; Seq a</span><span>
</span><span id="line-150"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#%3E%3C"><span class="hs-operator">(&gt;&lt;)</span></a></span><span class="hs-special">,</span><span>           </span><span class="hs-comment">-- :: Seq a -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-151"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#fromList"><span class="hs-identifier">fromList</span></a></span><span class="hs-special">,</span><span>       </span><span class="hs-comment">-- :: [a] -&gt; Seq a</span><span>
</span><span id="line-152"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#fromFunction"><span class="hs-identifier">fromFunction</span></a></span><span class="hs-special">,</span><span>   </span><span class="hs-comment">-- :: Int -&gt; (Int -&gt; a) -&gt; Seq a</span><span>
</span><span id="line-153"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#fromArray"><span class="hs-identifier">fromArray</span></a></span><span class="hs-special">,</span><span>      </span><span class="hs-comment">-- :: Ix i =&gt; Array i a -&gt; Seq a</span><span>
</span><span id="line-154"></span><span>    </span><span class="annot"><span class="hs-comment">-- ** Repetition</span></span><span>
</span><span id="line-155"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#replicate"><span class="hs-identifier">replicate</span></a></span><span class="hs-special">,</span><span>      </span><span class="hs-comment">-- :: Int -&gt; a -&gt; Seq a</span><span>
</span><span id="line-156"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#replicateA"><span class="hs-identifier">replicateA</span></a></span><span class="hs-special">,</span><span>     </span><span class="hs-comment">-- :: Applicative f =&gt; Int -&gt; f a -&gt; f (Seq a)</span><span>
</span><span id="line-157"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#replicateM"><span class="hs-identifier">replicateM</span></a></span><span class="hs-special">,</span><span>     </span><span class="hs-comment">-- :: Applicative m =&gt; Int -&gt; m a -&gt; m (Seq a)</span><span>
</span><span id="line-158"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#cycleTaking"><span class="hs-identifier">cycleTaking</span></a></span><span class="hs-special">,</span><span>    </span><span class="hs-comment">-- :: Int -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-159"></span><span>    </span><span class="annot"><span class="hs-comment">-- ** Iterative construction</span></span><span>
</span><span id="line-160"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#iterateN"><span class="hs-identifier">iterateN</span></a></span><span class="hs-special">,</span><span>       </span><span class="hs-comment">-- :: Int -&gt; (a -&gt; a) -&gt; a -&gt; Seq a</span><span>
</span><span id="line-161"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#unfoldr"><span class="hs-identifier">unfoldr</span></a></span><span class="hs-special">,</span><span>        </span><span class="hs-comment">-- :: (b -&gt; Maybe (a, b)) -&gt; b -&gt; Seq a</span><span>
</span><span id="line-162"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#unfoldl"><span class="hs-identifier">unfoldl</span></a></span><span class="hs-special">,</span><span>        </span><span class="hs-comment">-- :: (b -&gt; Maybe (b, a)) -&gt; b -&gt; Seq a</span><span>
</span><span id="line-163"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Deconstruction</span></span><span>
</span><span id="line-164"></span><span>    </span><span class="hs-comment">-- | Additional functions for deconstructing sequences are available</span><span>
</span><span id="line-165"></span><span>    </span><span class="hs-comment">-- via the 'Data.Foldable.Foldable' instance of 'Seq'.</span><span>
</span><span id="line-166"></span><span>
</span><span id="line-167"></span><span>    </span><span class="annot"><span class="hs-comment">-- ** Queries</span></span><span>
</span><span id="line-168"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#null"><span class="hs-identifier">null</span></a></span><span class="hs-special">,</span><span>           </span><span class="hs-comment">-- :: Seq a -&gt; Bool</span><span>
</span><span id="line-169"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#length"><span class="hs-identifier">length</span></a></span><span class="hs-special">,</span><span>         </span><span class="hs-comment">-- :: Seq a -&gt; Int</span><span>
</span><span id="line-170"></span><span>    </span><span class="annot"><span class="hs-comment">-- ** Views</span></span><span>
</span><span id="line-171"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#ViewL"><span class="hs-identifier">ViewL</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span>
</span><span id="line-172"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#viewl"><span class="hs-identifier">viewl</span></a></span><span class="hs-special">,</span><span>          </span><span class="hs-comment">-- :: Seq a -&gt; ViewL a</span><span>
</span><span id="line-173"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#ViewR"><span class="hs-identifier">ViewR</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span>
</span><span id="line-174"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#viewr"><span class="hs-identifier">viewr</span></a></span><span class="hs-special">,</span><span>          </span><span class="hs-comment">-- :: Seq a -&gt; ViewR a</span><span>
</span><span id="line-175"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Scans</span></span><span>
</span><span id="line-176"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#scanl"><span class="hs-identifier">scanl</span></a></span><span class="hs-special">,</span><span>          </span><span class="hs-comment">-- :: (a -&gt; b -&gt; a) -&gt; a -&gt; Seq b -&gt; Seq a</span><span>
</span><span id="line-177"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#scanl1"><span class="hs-identifier">scanl1</span></a></span><span class="hs-special">,</span><span>         </span><span class="hs-comment">-- :: (a -&gt; a -&gt; a) -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-178"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#scanr"><span class="hs-identifier">scanr</span></a></span><span class="hs-special">,</span><span>          </span><span class="hs-comment">-- :: (a -&gt; b -&gt; b) -&gt; b -&gt; Seq a -&gt; Seq b</span><span>
</span><span id="line-179"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#scanr1"><span class="hs-identifier">scanr1</span></a></span><span class="hs-special">,</span><span>         </span><span class="hs-comment">-- :: (a -&gt; a -&gt; a) -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-180"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Sublists</span></span><span>
</span><span id="line-181"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#tails"><span class="hs-identifier">tails</span></a></span><span class="hs-special">,</span><span>          </span><span class="hs-comment">-- :: Seq a -&gt; Seq (Seq a)</span><span>
</span><span id="line-182"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#inits"><span class="hs-identifier">inits</span></a></span><span class="hs-special">,</span><span>          </span><span class="hs-comment">-- :: Seq a -&gt; Seq (Seq a)</span><span>
</span><span id="line-183"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#chunksOf"><span class="hs-identifier">chunksOf</span></a></span><span class="hs-special">,</span><span>       </span><span class="hs-comment">-- :: Int -&gt; Seq a -&gt; Seq (Seq a)</span><span>
</span><span id="line-184"></span><span>    </span><span class="annot"><span class="hs-comment">-- ** Sequential searches</span></span><span>
</span><span id="line-185"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#takeWhileL"><span class="hs-identifier">takeWhileL</span></a></span><span class="hs-special">,</span><span>     </span><span class="hs-comment">-- :: (a -&gt; Bool) -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-186"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#takeWhileR"><span class="hs-identifier">takeWhileR</span></a></span><span class="hs-special">,</span><span>     </span><span class="hs-comment">-- :: (a -&gt; Bool) -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-187"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#dropWhileL"><span class="hs-identifier">dropWhileL</span></a></span><span class="hs-special">,</span><span>     </span><span class="hs-comment">-- :: (a -&gt; Bool) -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-188"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#dropWhileR"><span class="hs-identifier">dropWhileR</span></a></span><span class="hs-special">,</span><span>     </span><span class="hs-comment">-- :: (a -&gt; Bool) -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-189"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#spanl"><span class="hs-identifier">spanl</span></a></span><span class="hs-special">,</span><span>          </span><span class="hs-comment">-- :: (a -&gt; Bool) -&gt; Seq a -&gt; (Seq a, Seq a)</span><span>
</span><span id="line-190"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#spanr"><span class="hs-identifier">spanr</span></a></span><span class="hs-special">,</span><span>          </span><span class="hs-comment">-- :: (a -&gt; Bool) -&gt; Seq a -&gt; (Seq a, Seq a)</span><span>
</span><span id="line-191"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#breakl"><span class="hs-identifier">breakl</span></a></span><span class="hs-special">,</span><span>         </span><span class="hs-comment">-- :: (a -&gt; Bool) -&gt; Seq a -&gt; (Seq a, Seq a)</span><span>
</span><span id="line-192"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#breakr"><span class="hs-identifier">breakr</span></a></span><span class="hs-special">,</span><span>         </span><span class="hs-comment">-- :: (a -&gt; Bool) -&gt; Seq a -&gt; (Seq a, Seq a)</span><span>
</span><span id="line-193"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#partition"><span class="hs-identifier">partition</span></a></span><span class="hs-special">,</span><span>      </span><span class="hs-comment">-- :: (a -&gt; Bool) -&gt; Seq a -&gt; (Seq a, Seq a)</span><span>
</span><span id="line-194"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#filter"><span class="hs-identifier">filter</span></a></span><span class="hs-special">,</span><span>         </span><span class="hs-comment">-- :: (a -&gt; Bool) -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-195"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Sorting</span></span><span>
</span><span id="line-196"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#sort"><span class="hs-identifier">sort</span></a></span><span class="hs-special">,</span><span>           </span><span class="hs-comment">-- :: Ord a =&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-197"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#sortBy"><span class="hs-identifier">sortBy</span></a></span><span class="hs-special">,</span><span>         </span><span class="hs-comment">-- :: (a -&gt; a -&gt; Ordering) -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-198"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#sortOn"><span class="hs-identifier">sortOn</span></a></span><span class="hs-special">,</span><span>         </span><span class="hs-comment">-- :: Ord b =&gt; (a -&gt; b) -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-199"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#unstableSort"><span class="hs-identifier">unstableSort</span></a></span><span class="hs-special">,</span><span>   </span><span class="hs-comment">-- :: Ord a =&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-200"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#unstableSortBy"><span class="hs-identifier">unstableSortBy</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-comment">-- :: (a -&gt; a -&gt; Ordering) -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-201"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html#unstableSortOn"><span class="hs-identifier">unstableSortOn</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-comment">-- :: Ord b =&gt; (a -&gt; b) -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-202"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Indexing</span></span><span>
</span><span id="line-203"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#lookup"><span class="hs-identifier">lookup</span></a></span><span class="hs-special">,</span><span>         </span><span class="hs-comment">-- :: Int -&gt; Seq a -&gt; Maybe a</span><span>
</span><span id="line-204"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#%21%3F"><span class="hs-operator">(!?)</span></a></span><span class="hs-special">,</span><span>           </span><span class="hs-comment">-- :: Seq a -&gt; Int -&gt; Maybe a</span><span>
</span><span id="line-205"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#index"><span class="hs-identifier">index</span></a></span><span class="hs-special">,</span><span>          </span><span class="hs-comment">-- :: Seq a -&gt; Int -&gt; a</span><span>
</span><span id="line-206"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#adjust"><span class="hs-identifier">adjust</span></a></span><span class="hs-special">,</span><span>         </span><span class="hs-comment">-- :: (a -&gt; a) -&gt; Int -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-207"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#adjust%27"><span class="hs-identifier">adjust'</span></a></span><span class="hs-special">,</span><span>        </span><span class="hs-comment">-- :: (a -&gt; a) -&gt; Int -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-208"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#update"><span class="hs-identifier">update</span></a></span><span class="hs-special">,</span><span>         </span><span class="hs-comment">-- :: Int -&gt; a -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-209"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#take"><span class="hs-identifier">take</span></a></span><span class="hs-special">,</span><span>           </span><span class="hs-comment">-- :: Int -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-210"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#drop"><span class="hs-identifier">drop</span></a></span><span class="hs-special">,</span><span>           </span><span class="hs-comment">-- :: Int -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-211"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#insertAt"><span class="hs-identifier">insertAt</span></a></span><span class="hs-special">,</span><span>       </span><span class="hs-comment">-- :: Int -&gt; a -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-212"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#deleteAt"><span class="hs-identifier">deleteAt</span></a></span><span class="hs-special">,</span><span>       </span><span class="hs-comment">-- :: Int -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-213"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#splitAt"><span class="hs-identifier">splitAt</span></a></span><span class="hs-special">,</span><span>        </span><span class="hs-comment">-- :: Int -&gt; Seq a -&gt; (Seq a, Seq a)</span><span>
</span><span id="line-214"></span><span>    </span><span class="annot"><span class="hs-comment">-- ** Indexing with predicates</span></span><span>
</span><span id="line-215"></span><span>    </span><span class="hs-comment">-- | These functions perform sequential searches from the left</span><span>
</span><span id="line-216"></span><span>    </span><span class="hs-comment">-- or right ends of the sequence, returning indices of matching</span><span>
</span><span id="line-217"></span><span>    </span><span class="hs-comment">-- elements.</span><span>
</span><span id="line-218"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#elemIndexL"><span class="hs-identifier">elemIndexL</span></a></span><span class="hs-special">,</span><span>     </span><span class="hs-comment">-- :: Eq a =&gt; a -&gt; Seq a -&gt; Maybe Int</span><span>
</span><span id="line-219"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#elemIndicesL"><span class="hs-identifier">elemIndicesL</span></a></span><span class="hs-special">,</span><span>   </span><span class="hs-comment">-- :: Eq a =&gt; a -&gt; Seq a -&gt; [Int]</span><span>
</span><span id="line-220"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#elemIndexR"><span class="hs-identifier">elemIndexR</span></a></span><span class="hs-special">,</span><span>     </span><span class="hs-comment">-- :: Eq a =&gt; a -&gt; Seq a -&gt; Maybe Int</span><span>
</span><span id="line-221"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#elemIndicesR"><span class="hs-identifier">elemIndicesR</span></a></span><span class="hs-special">,</span><span>   </span><span class="hs-comment">-- :: Eq a =&gt; a -&gt; Seq a -&gt; [Int]</span><span>
</span><span id="line-222"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#findIndexL"><span class="hs-identifier">findIndexL</span></a></span><span class="hs-special">,</span><span>     </span><span class="hs-comment">-- :: (a -&gt; Bool) -&gt; Seq a -&gt; Maybe Int</span><span>
</span><span id="line-223"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#findIndicesL"><span class="hs-identifier">findIndicesL</span></a></span><span class="hs-special">,</span><span>   </span><span class="hs-comment">-- :: (a -&gt; Bool) -&gt; Seq a -&gt; [Int]</span><span>
</span><span id="line-224"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#findIndexR"><span class="hs-identifier">findIndexR</span></a></span><span class="hs-special">,</span><span>     </span><span class="hs-comment">-- :: (a -&gt; Bool) -&gt; Seq a -&gt; Maybe Int</span><span>
</span><span id="line-225"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#findIndicesR"><span class="hs-identifier">findIndicesR</span></a></span><span class="hs-special">,</span><span>   </span><span class="hs-comment">-- :: (a -&gt; Bool) -&gt; Seq a -&gt; [Int]</span><span>
</span><span id="line-226"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Folds</span></span><span>
</span><span id="line-227"></span><span>    </span><span class="hs-comment">-- | General folds are available via the 'Data.Foldable.Foldable' instance</span><span>
</span><span id="line-228"></span><span>    </span><span class="hs-comment">-- of 'Seq'.</span><span>
</span><span id="line-229"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#foldMapWithIndex"><span class="hs-identifier">foldMapWithIndex</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-comment">-- :: Monoid m =&gt; (Int -&gt; a -&gt; m) -&gt; Seq a -&gt; m</span><span>
</span><span id="line-230"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#foldlWithIndex"><span class="hs-identifier">foldlWithIndex</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-comment">-- :: (b -&gt; Int -&gt; a -&gt; b) -&gt; b -&gt; Seq a -&gt; b</span><span>
</span><span id="line-231"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#foldrWithIndex"><span class="hs-identifier">foldrWithIndex</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-comment">-- :: (Int -&gt; a -&gt; b -&gt; b) -&gt; b -&gt; Seq a -&gt; b</span><span>
</span><span id="line-232"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Transformations</span></span><span>
</span><span id="line-233"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#mapWithIndex"><span class="hs-identifier">mapWithIndex</span></a></span><span class="hs-special">,</span><span>   </span><span class="hs-comment">-- :: (Int -&gt; a -&gt; b) -&gt; Seq a -&gt; Seq b</span><span>
</span><span id="line-234"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#traverseWithIndex"><span class="hs-identifier">traverseWithIndex</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-comment">-- :: Applicative f =&gt; (Int -&gt; a -&gt; f b) -&gt; Seq a -&gt; f (Seq b)</span><span>
</span><span id="line-235"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#reverse"><span class="hs-identifier">reverse</span></a></span><span class="hs-special">,</span><span>        </span><span class="hs-comment">-- :: Seq a -&gt; Seq a</span><span>
</span><span id="line-236"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#intersperse"><span class="hs-identifier">intersperse</span></a></span><span class="hs-special">,</span><span>    </span><span class="hs-comment">-- :: a -&gt; Seq a -&gt; Seq a</span><span>
</span><span id="line-237"></span><span>    </span><span class="annot"><span class="hs-comment">-- ** Zips and unzip</span></span><span>
</span><span id="line-238"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#zip"><span class="hs-identifier">zip</span></a></span><span class="hs-special">,</span><span>            </span><span class="hs-comment">-- :: Seq a -&gt; Seq b -&gt; Seq (a, b)</span><span>
</span><span id="line-239"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#zipWith"><span class="hs-identifier">zipWith</span></a></span><span class="hs-special">,</span><span>        </span><span class="hs-comment">-- :: (a -&gt; b -&gt; c) -&gt; Seq a -&gt; Seq b -&gt; Seq c</span><span>
</span><span id="line-240"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#zip3"><span class="hs-identifier">zip3</span></a></span><span class="hs-special">,</span><span>           </span><span class="hs-comment">-- :: Seq a -&gt; Seq b -&gt; Seq c -&gt; Seq (a, b, c)</span><span>
</span><span id="line-241"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#zipWith3"><span class="hs-identifier">zipWith3</span></a></span><span class="hs-special">,</span><span>       </span><span class="hs-comment">-- :: (a -&gt; b -&gt; c -&gt; d) -&gt; Seq a -&gt; Seq b -&gt; Seq c -&gt; Seq d</span><span>
</span><span id="line-242"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#zip4"><span class="hs-identifier">zip4</span></a></span><span class="hs-special">,</span><span>           </span><span class="hs-comment">-- :: Seq a -&gt; Seq b -&gt; Seq c -&gt; Seq d -&gt; Seq (a, b, c, d)</span><span>
</span><span id="line-243"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#zipWith4"><span class="hs-identifier">zipWith4</span></a></span><span class="hs-special">,</span><span>       </span><span class="hs-comment">-- :: (a -&gt; b -&gt; c -&gt; d -&gt; e) -&gt; Seq a -&gt; Seq b -&gt; Seq c -&gt; Seq d -&gt; Seq e</span><span>
</span><span id="line-244"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#unzip"><span class="hs-identifier">unzip</span></a></span><span class="hs-special">,</span><span>          </span><span class="hs-comment">-- :: Seq (a, b) -&gt; (Seq a, Seq b)</span><span>
</span><span id="line-245"></span><span>    </span><span class="annot"><a href="Data.Sequence.Internal.html#unzipWith"><span class="hs-identifier">unzipWith</span></a></span><span>       </span><span class="hs-comment">-- :: (a -&gt; (b, c)) -&gt; Seq a -&gt; (Seq b, Seq c)</span><span>
</span><span id="line-246"></span><span>    </span><span class="hs-special">)</span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-247"></span><span>
</span><span id="line-248"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.html"><span class="hs-identifier">Data.Sequence.Internal</span></a></span><span>
</span><span id="line-249"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="Data.Sequence.Internal.Sorting.html"><span class="hs-identifier">Data.Sequence.Internal.Sorting</span></a></span><span>
</span><span id="line-250"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Prelude.html#"><span class="hs-identifier">Prelude</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-special">)</span><span class="hs-cpp">
#ifdef __HADDOCK_VERSION__
</span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Control.Monad.html#"><span class="hs-identifier">Control.Monad</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/GHC.Base.html#Monad"><span class="hs-identifier">Monad</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-253"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Control.Applicative.html#"><span class="hs-identifier">Control.Applicative</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/GHC.Base.html#Applicative"><span class="hs-identifier">Applicative</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-254"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Data.Functor.html#"><span class="hs-identifier">Data.Functor</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/GHC.Base.html#Functor"><span class="hs-identifier">Functor</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">)</span><span class="hs-cpp">
#endif
</span><span>
</span><span id="line-257"></span><span class="hs-comment">{- $patterns

== Pattern synonyms

Much like lists can be constructed and matched using the
@:@ and @[]@ constructors, sequences can be constructed and
matched using the 'Empty', ':&lt;|', and ':|&gt;' pattern synonyms.

=== Note

These patterns are only available with GHC version 8.0 or later,
and version 8.2 works better with them. When writing for such recent
versions of GHC, the patterns can be used in place of 'empty',
'&lt;|', '|&gt;', 'viewl', and 'viewr'.

=== __Pattern synonym examples__

Import the patterns:

@
import Data.Sequence (Seq (..))
@

Look at the first three elements of a sequence

@
getFirst3 :: Seq a -&gt; Maybe (a,a,a)
getFirst3 (x1 :&lt;| x2 :&lt;| x3 :&lt;| _xs) = Just (x1,x2,x3)
getFirst3 _ = Nothing
@

@
\&gt; getFirst3 ('fromList' [1,2,3,4]) = Just (1,2,3)
\&gt; getFirst3 ('fromList' [1,2]) = Nothing
@

Move the last two elements from the end of the first list
onto the beginning of the second one.

@
shift2Right :: Seq a -&gt; Seq a -&gt; (Seq a, Seq a)
shift2Right Empty ys = (Empty, ys)
shift2Right (Empty :|&gt; x) ys = (Empty, x :&lt;| ys)
shift2Right (xs :|&gt; x1 :|&gt; x2) = (xs, x1 :&lt;| x2 :&lt;| ys)
@

@
\&gt; shift2Right ('fromList' []) ('fromList' [10]) = ('fromList' [], 'fromList' [10])
\&gt; shift2Right ('fromList' [9]) ('fromList' [10]) = ('fromList' [], 'fromList' [9,10])
\&gt; shift2Right ('fromList' [8,9]) ('fromList' [10]) = ('fromList' [], 'fromList' [8,9,10])
\&gt; shift2Right ('fromList' [7,8,9]) ('fromList' [10]) = ('fromList' [7], 'fromList' [8,9,10])
@
-}</span><span>
</span><span id="line-310"></span></pre></body></html>